/*
 * @lc app=leetcode.cn id=3186 lang=cpp
 * @lcpr version=30204
 *
 * [3186] 施咒的最大总伤害
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        // 统计每个伤害值的出现次数
        unordered_map<int, int> cnt;
        for (int x : power) {
            cnt[x]++;
        }

        // 去重并排序
        vector<pair<int, int>> a(cnt.begin(), cnt.end());
        ranges::sort(a);

        int n = a.size();
        vector<long long> f(n + 1);  // 动态规划数组
        for (int i = 0, j = 0; i < n; i++) {
            auto& [x, c] = a[i];
            // 找到第一个不小于 x-2 的位置 j
            while (a[j].first < x - 2) {
                j++;
            }
            // 状态转移：不选x（f[i]）或选x（f[j] + x*c）
            f[i + 1] = max(f[i], f[j] + (long long) x * c);
        }
        return f[n];
    }
};
// @lc code=end



/*
// @lcpr case=start
// [1,1,3,4]\n
// @lcpr case=end

// @lcpr case=start
// [7,1,6,6]\n
// @lcpr case=end

 */

